package selection;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: zhangQi
 * @Date: 2020-09-19 14:24
 */
public class SelectionSort {

    public static void main(String[] args) {
        List<Integer> arr = new ArrayList<>(Arrays.asList(5,3,6,2,10,9,52,13,1));
        System.out.println(selectionSort(arr));
    }

    private static List<Integer> selectionSort(List<Integer> arr) {
        List<Integer> newArr = new ArrayList<>(arr.size());
        //get size of the array
        int size = arr.size();

        for (int i = 0; i < size; i++) {
            /**
             * 循环遍历,查找最小数值下标
             */
            int smallest = findSmallest(arr);
            /**
             * 新数组一个一个放入最小的数据
             */
            newArr.add(arr.get(smallest));
            /**
             * 旧数组中一个一个移除指定下标的数据(每次最小的),节省了获取最小数据的遍历次数
             */
            arr.remove(smallest);
        }
        return newArr;
    }


    /**
     * 获取数据中最小数的下标
     * @param arr
     * @return
     */
    private static int findSmallest(List<Integer> arr) {
        int smallest = arr.get(0);
        int smallestIndex = 0;
        for(int i=0;i<arr.size();i++){
            if(arr.get(i)<smallest){
                smallest = arr.get(i);
                smallestIndex = i;
            }
        }
        return smallestIndex;
    }
}
